Computability Theory

定义 Definition

可计算性理论：计算机科学与数理逻辑的分支，研究“哪些问题可以被算法在有限步骤内解决”、以及可计算性的边界（如不可判定问题、图灵机、递归函数、归约与复杂度层次等）。常与“递归论（recursion theory）”有密切关系。

发音 Pronunciation (IPA)

/kəmˌpjuːtəˈbɪləti ˈθɪəri/

例句 Examples

Computability theory studies what problems an algorithm can solve.
可计算性理论研究算法能够解决哪些问题。

Using computability theory, we can prove that some questions have no general algorithmic solution, such as the halting problem.
借助可计算性理论，我们可以证明有些问题不存在通用的算法解法，例如停机问题。

词源 Etymology

computability 来自 compute（计算）+ 后缀 -ability（能力、可……性），表示“可被计算/可通过算法完成的性质”。theory 源自希腊语 theōria（观察、思考），在现代学术语境中指系统化的理论体系。合起来，computability theory 即“关于可计算性的理论研究”。

相关词 Related Words

• Algorithm
• Decidability
• Undecidable
• Turing Machine
• Halting Problem
• Reduction
• Recursion
• Formal Language
• Complexity Theory

文献与作品 Literary / Notable Works

• Alan M. Turing：《On Computable Numbers, with an Application to the Entscheidungsproblem》（1936）——奠定可计算性理论核心概念。
• Stephen C. Kleene：《Introduction to Metamathematics》（1952）——系统介绍递归函数与可计算性的经典著作。
• Hartley Rogers Jr.：《Theory of Recursive Functions and Effective Computability》（1967）——可计算性/递归论的重要教材与参考书。
• Michael Sipser：《Introduction to the Theory of Computation》——计算理论入门教材，含可计算性理论的标准章节。